1. Field of the Invention
The present invention relates to a method and device for controlling a cache memory and, particularly, to a method and device for controlling a cache memory, in such a way that an information such as instructions and/or data, etc., which is requested by a processor, is read out from a cache memory or a main memory and supplied to the processor.
2. Description of Related Art
FIG. 9 is a block circuit diagram showing an example of an electrical construction of a main portion of a data processor to which a conventional cache memory control device is applied.
The data processor shown in FIG. 9 is constructed with, mainly, a processor 1, a cache memory control device 2 and a main memory device 3. The cache memory control device 2 is constructed with, mainly, a cache memory 4, a tag memory 5, an address generator circuit 6, a comparator 7, buffers 8 to 11, an LRU (Least Recently Used) information generator circuit 12 and an LRU memory 13.
The processor 1 performs a data processing by controlling various portions of the data processor. The cache memory control device 2 reads out an information such as instructions and/or data, etc., which is requested by the processor 1, from the cache memory 4 or the main memory device 3, as occasion demands, and supplies the information thus read out to the processor 1. The information such as instructions and/or data, etc., which are necessary for the processor 1 to perform a data processing, is stored in the main memory device 3.
The cache memory 4 temporarily stores the information such as instructions and/or data, etc., which is read out from the main memory device 3. In order to search the information stored in the cache memory 4, the tag memory 5 stores a tag, which is a portion of an address of the information. The address generator circuit 6 generates an address necessary to read the information, to which the processor 1 requests an access, from the main memory device 3, in a case of xe2x80x9cmishitxe2x80x9d, that is, when the information is not stored in the cache memory 4. The comparator 7 compares the tag which is a portion of the address supplied from the processor 1 with a plurality of tags read out from the tag memory 5 and outputs a hit information in a case of xe2x80x9chitxe2x80x9d, that is, when the information requested by the processor 1 is stored in the cache memory 4 and a tag, which is the same as the tag, is found in the tags read out from the tag memory. The buffer 8 temporarily stores the address supplied from the processor 1. The buffer 9 temporarily stores the hit information supplied from the comparator 7. Buffer 10 temporarily stores the information read out from the cache memory 4. The buffer 11 temporarily stores the address generated by the address generator circuit 6. The buffers 8 to 11 are constructed with latches and flip-flops, etc., respectively. In order to effectively utilize the cache memory 4, the LRU information generator circuit 12 generates, on the basis of the hit information read out from the buffer 9, an LRU information indicating that an information among the information stored in the cache memory 4, which is not used for the longest time, is replaced by an information newly read out from the main memory device 3. The LRU information is stored in an address of the LRU memory 13, which address is read out from the buffer 8.
An operation of the cache memory control device constructed as mentioned above will be described. First, when the processor 1 requests an access to a certain information and supplies a certain address to the cache memory control device 2, the address is temporarily stored in the buffer 8. The same address is also supplied to the cache memory 4 and the tag memory 5. Therefore, a tag corresponding to the address is read out from the tag memory 5. The comparator 7 compares the tag corresponding to a portion of the address supplied from the processor 1 with a plurality of tags read out from the tag memory a and outputs a hit information in a case of xe2x80x9chitxe2x80x9d, that is, when the information requested by the processor 1 is stored in the cache memory 4 and a tag, which is the same as the tag corresponding to the portion of the address from the processor, is found in the tags read out from the tag memory. The buffer 9 temporarily stores the hit information supplied from the comparator 7. Simultaneously with this processing, an information corresponding to the address is read out from the cache memory 4 when it is hit and is temporarily stored in the buffer 10. The above mentioned processing up to the temporary storage of the information in the buffer 10 will be referred to as xe2x80x9cfirst processingxe2x80x9d.
Then, the LRU information generator circuit 12 generates the LRU information on the basis of the hit information read out from the buffer 9 and the LRU information is stored in the address in the LRU memory 13, which is read out from the buffer 8. In the case of hit, the information temporarily stored in the buffer 10 is supplied to the processor 1. This processing will be referred to as xe2x80x9csecond processingxe2x80x9d.
The above mentioned first and second processing are executed in pipe-line.
On the other hand, in the case of mishit, the address generator 6 generates an address for reading an information corresponding to the address from the main memory device 3 and the this generated address is temporarily stored in the buffer 11. Therefore, the address temporarily stored in the buffer 11 is read out and supplied to the main memory device 3. Thus, the information corresponding to the address supplied from the main memory device 3 is read out and stored in the cache memory 4. Subsequently, the first processing and the second processing are executed.
When an address corresponding to an access request related to a certain information is supplied from the processor 1 in the conventional cache memory control device 2 mentioned above, it takes a time corresponding to at least one clock from the supply of the address An (n=1, 2, 3, . . . ) up to a time at which a search for a tag corresponding to the address in the tag memory 5 ends (see FIG. 10(1)). Therefore, in the case of hit, it takes a time corresponding to at least 1 clock to read out the requested information Dn (n=1, 2, 3, . . . ) from the cache memory 4 (see FIG. 10(2)). Thus, there is a defect that it is impossible to immediately respond to an access request from the processor 1, even when the information is stored in the cache memory 4.
Further, when there are successive hits in the described conventional cache memory control device 2, the cache memory 4, the tag memory 5 and the LRU memory 13 are always accessed with considerable power consumption since the reading of the information (see FIG. 10(2)), the reading of the tag (see FIG. 10(3)) and the update of the LRU information (see FIG. 10(4)) are executed in pipe line processing. Therefore, when the processor 1 and the cache memory control device 2 are constructed as a single IC chip, operating temperature of the IC chip is increased, causing the life thereof to be shortened. In order to solve this problem, a heat radiator or a fan has to be provided, resulting in another defect that the data processing device becomes high in cost and large in size.
The present invention was made in view of the above mentioned state of art and an object of the present invention is to provide a method and device for controlling a cache memory, with which a quick response to an access request from a processor is realized with reduced power consumption.
In order to achieve the above object, a cache memory control method according to a first aspect of the present invention, which is used in a cache memory control device including a cache memory storing an information, a tag memory storing tags constructing addresses corresponding to the information stored in the cache memory and at least one buffer for temporarily storing tags read out from the tag memory. The cache memory control method is adapted to read out an information requested by a processor from the cache memory or a main memory device and supply it to the processor. The cache memory control method of the present invention is featured by comprising the steps of reading at least one of the tags stored in the tag memory, which tag constitutes an address corresponding to an information predicted as to be requested next by the processor, on the basis of the address corresponding to the information requested next by the processor, temporarily storing the tag read out from the tag memory in the buffer and comparing the tag constituting the address supplied next from the processor with the tag temporarily stored in the buffer, before the tag constituting the address supplied next from the processor is read out from the tag memory.
According to a second aspect of the present invention, in the cache memory control method according to the first aspect, the tag constituting the address corresponding to the information predicted as to be requested next by the processor is one of a tag corresponding to the information currently requested by the processor, a tag adjacent to the tag, a tag corresponding to an information requested past by the processor and a tag constituting an address corresponding to the information when an information stored in a discontinuous memory region of the main memory device is requested by the processor, or a combination of these tags.
A third aspect of the present invention resides in a cache memory control method, which is used in a cache memory control device including a cache memory storing an information, a tag memory storing tags constituting addresses corresponding to the information stored in the cache memory, a first buffer for temporarily storing tags read out from the tag memory, a second buffer for temporarily storing an information read out from the main memory device and a third buffer for temporarily storing addresses temporarily stored in the second buffer. The cache memory control method according to the third aspect of the present invention is adapted to read out an information requested by a processor from the cache memory or a main memory device and supply it to the processor. The cache memory control method according to the third aspect of the present invention is featured by comprising a first processing composed of the steps of reading an information from the cache memory or the second buffer and supplying it to the processor when an address corresponding to a requested information supplied from the processor or a tag constituting the same address coincides with the address temporarily stored in the third buffer or the tag temporarily stored in the first buffer, or reading out the tag constituting the address supplied from the processor from the tag memory and temporarily storing it in the first buffer when the address corresponding to the requested information supplied from the processor or the tag constituting the same address does not coincide with the address temporarily stored in the third buffer or the tag temporarily stored in the first buffer stored in the cache memory, and a second processing composed of the steps of reading an information from the cache memory and supplying it to the processor when the tag constituting the address supplied from the processor coincides with the tag temporarily held in the first buffer in the first processing, or reading out the information from the main memory device on the basis of the address supplied from the processor, temporarily storing the information in the second buffer and the cache memory and temporarily holding the address of the information temporarily held in the second buffer in the third buffer when the tag constituting the address supplied from the processor does not coincide with the tag temporarily held in the first buffer in the first processing.
A fourth aspect of the present invention is featured by that, in the third aspect, the cache memory control device further includes a fourth buffer for temporarily storing a tag of an information predicted as to be requested next by the processor, which is read out from the tag memory, that a third processing for reading the tag of the information predicted as to be requested next by the processor from the tag memories and temporarily storing the tag in the fourth buffer and that, in the first processing, one of the address temporarily stored in the third buffer and the tags temporarily stored in the first and fourth buffers is determined as being coincident with the address supplied from the processor or the tag constituting the address.
According to a fifth aspect of the present invention, a cache memory control method for reading an information requested by a processor from a cache memory or a main memory and supplying the information to the processor, the cache memory control device including tag memories for storing tags constituting addresses corresponding to information stored in the cache memory, a tag buffer for temporarily storing a tag read out from the tag memories, an information buffer for temporarily storing an information read out from the main memory, a backup buffer for temporarily storing an address of the information temporarily stored in the information buffer, a last buffer for temporarily storing a newest tag, a next buffer for temporarily storing a tag adjacent to the tag constituting the address supplied from said processor and corresponding to the information requested thereby and a branch buffer for temporarily storing a tag constituting an address of an information temporarily stored in a discontinuous memory region of said main memory when the information is requested by the processor. The cache memory control method comprises a first processing for reading the information from the cache memory or the information buffer and supplying the information to the processor when an address supplied from the processor or a tag constituting the address is coincident with an address temporarily stored in the backup buffer or a tag temporarily stored in the last buffer, the next buffer or the branch buffer, a second processing for reading the information from the cache memory and supplying the information to the processor when the tag constituting the address supplied from the processor is coincident with the tag temporarily stored in the tag buffer, a third processing reading the information from the main memory on the basis of the address supplied from the processor, temporarily storing the information in the information buffer and in the cache memory and temporarily storing addresses of the information temporarily stored in the information buffer in the backup buffer, a fourth processing for reading the tag constituting the address supplied from the processor from the tag memories and temporarily storing the tag in the tag buffer and a fifth processing for reading the tag adjacent to the tag constituting the address supplied from the processor and temporarily storing the adjacent tag in the next buffer, and, the information stored in the discontinuous memory region of the main memory is requested by the processor, temporarily storing the tag constituting the address corresponding to the information in the branch buffer and, otherwise, temporarily storing the information in the last buffer.
According to a sixth aspect of the present invention, in the cache memory control method according to the fifth aspect, the first to third processing are performed in parallel to the fourth and fifth processing independently therefrom.
According to a seventh aspect of the present invention, in the cache memory control method according to the fifth or sixth aspect, the cache memory is composed of a plurality of ways each composed of a plurality of entries for storing a plurality of information. The next buffer and the tag buffer are provided for each way, respectively, the information buffer is provided for each of information stored in each of the entries. In the third processing, all information constituting the entries to which the informations belong are read out from the main memory and temporarily stored in the plurality of the information buffers.
According to an eighth aspect of the present invention, a cache memory control device for reading an information requested by a processor from a cache memory or a main memory and supplying the information to said processor, comprises tag memories for storing tags constituting addresses corresponding to information stored in the cache memory, at least one buffer for reading a tag constituting an address corresponding to an information predicted as to be requested next by the processor, on a basis of an address supplied from the processor and corresponding to a requested information, and temporarily storing the tag in at least one of the tag memories and a comparator for comparing the tag constituting the address supplied next by the processor with the tag temporarily stored in the buffer, before the tag constituting the address supplied next by the processor is read out from the at least one of the tag memories.
According to a ninth aspect of the present invention, in the cache memory control device according to the eighth aspect, the tag constituting the address corresponding to the information predicted as to be requested next by said processor is one of a tag corresponding to an information currently requested by the processor, a tag adjacent to the tag corresponding to the information currently requested by the processor, a tag corresponding to an information requested by the processor in the past and a tag constituting an address corresponding to an information in a case where the information stored in a discontinuous memory region of the main memory is requested by the processor, or a combination of these tags.
According to a tenth aspect of the present invention, a cache memory control device for reading an information requested by a processor from a cache memory or a main memory and supplying the information to the processor, comprises tag memories for storing tags constituting addresses corresponding to information stored in the cache memory, a first buffer for temporarily storing a tag read out from the tag memories, a second buffer for temporarily storing an information read out from the main memory, a third buffer for temporarily storing an address of an information temporarily stored in the second buffer, a first comparator for comparing a tag constituting an address supplied from the processor and corresponding to an information requested by the processor with a tag temporarily stored in the first buffer and outputting a hit signal when the tags are coincident, a second comparator for comparing the address supplied from the processor with the address temporarily stored in the third buffer and outputting a hit signal when the addresses are coincident. The information is read out from the cache memory or the second buffer and supplied to the processor when either the first or second comparator outputs a hit signal, the tag constituting the address supplied from the processor is read out from the tag memory and temporarily stored in the first buffer when neither the first nor second comparator outputs a hit signal, the information read out from the cache memory and supplied to the processor when the first comparator outputs the hit signal, or the information is read out from the main memory on the basis of the address supplied from the processor and temporarily stored in the second buffer and the cache memory and the address of the information temporarily stored in the second buffer is temporarily stored in the third buffer when the first comparator outputs no hit signal.
According to an eleventh aspect to the present invention, in the tenth aspect, the cache memory control device further comprises a fourth buffer for temporarily storing a tag of an information predicted as to be requested next by the processor and read out from the tag memories and a third comparator for comparing the tag constituting the address supplied from the processor with the tag temporarily stored in the fourth buffer and outputting a hit signal when the tags are coincident. The information is read out from the cache memory or the second buffer and supplied to the processor when the first to third comparators output the hit signals, the tag constituting the address supplied from the processor is read out from the tag memory and temporarily stored in the first buffer and a tag of an information predicted as to be requested next by the processor is read out from the tag memory and temporarily stored in the fourth buffer when the first to third comparators outputs no hit signal, the information is read out from the cache memory and supplied to the processor when the first comparator outputs the hit signal, or the information is read out from the main memory on the basis of the address supplied from the processor and temporarily stored in the second buffer and the cache memory and the address of the information temporarily stored in the second buffer is temporarily stored in the third buffer when the first comparator outputs no hit signal.
According to a twelfth aspect of the present invention, a cache memory control device for reading an information requested by a processor from a cache memory or a main memory and supplying the information to the processor, comprises tag memories for storing tags constituting addresses corresponding to information stored in the cache memory, a tag buffer for temporarily storing a tag read out from the tag memories, an information buffer for temporarily storing an information read out from the main memory, a backup buffer for temporarily storing an address of an information temporarily stored in the information buffer, a last buffer for temporarily storing a newest tag, a next buffer for temporarily storing a tag adjacent to the tag constituting an address supplied from the processor and corresponding to an information requested by the processor, a branch buffer for temporarily storing a tag constituting an address of an information temporarily stored in a discontinuous memory region of the main memory when the information is requested by the processor, a first, second, third and fourth comparators each for comparing a tag constituting an address supplied from the processor and corresponding to an information requested by the processor with a tag temporarily stored in different one of the tag buffer, the last buffer, the next buffer and the branch buffer and outputting a hit signal when the tags are coincident and a fifth comparator for comparing the address supplied from the processor with the address temporarily stored in the backup buffer and outputting a hit signal when the addresses are coincident. The cache memory control device takes in a first state in which, when the second to fifth comparators output the hit signals, the information is read out from the cache memory or the information buffer and supplied to the processor, a second state in which, when the first comparator outputs the hit signal, the information is read out from the cache memory and supplied to the processor, a third state in which the information is read out from the main memory on the basis of the address supplied from the processor, temporarily storing the information in the information buffer and in the cache memory and addresses of the information temporarily stored in the information buffer are temporarily stored in the backup buffer, a fourth state in which the tag constituting the address supplied from the processor is read out from the tag memories and temporarily stored in the tag buffer and a fifth state in which the tag adjacent to the tag constituting the address supplied from the processor is read out from the tag memories and temporarily stored in the next buffer, and, when the information stored in the discontinuous memory region of the main memory is requested by the processor, the tag constituting the address corresponding to the information is temporarily stored in the branch buffer and, otherwise, the tag constituting the address corresponding to the information is temporarily stored in the last buffer.
According to a thirteenth aspect of the present invention, the first to third states of the cache memory control device according to the twelfth aspect are in parallel to the fourth and fifth states independently therefrom.
According to a fourteenth aspect of the present invention, the cache memory of the cache memory control device according to the twelfth or thirteenth aspect is composed of a plurality of ways each composed of a plurality of entries for storing a plurality of information. The next buffer, the tag buffer and the first and third comparators are provided for each way, respectively, the information buffer is provided for each of information stored in each of the entries, and a predetermined number of the branch buffers and a predetermined number of the fourth comparators are provided. In the third state, all information constituting the entries to which the information belong are read out from the main memory and temporarily stored in the plurality of the information buffers.
According to the construction of the present invention, it is possible to immediately respond to an access request from a processor and to reduce power consumption.